package algorithm.arithmetic.字符串表达式计算;

import java.util.Collections;
import java.util.Stack;

/**
 * @author xinchen by 2016/11/25
 * @version 1.0
 */
public class Solution {


    // 设计一种结构或算法实现字符串表达式的运算功能，表达式支持+、-、*、/、%、()、[]。请勿使用脚本引擎实现。
    public static void main(String[] args) {
        // 使用后缀表达式计算
        String expression = args[0];
        Stack<String> suffixExpression = getSuffixExpression(expression);
        Integer result = computeSuffixExpression(suffixExpression);
        System.out.println(result);

    }

    private static Integer computeSuffixExpression(Stack<String> suffixExpression) {
        Stack<Integer> computeStack = new Stack<Integer>();
        while (!suffixExpression.isEmpty()) {
            String exp = suffixExpression.pop();
            if (Character.isDigit(exp.charAt(0))) {
                // 如果是操作数，直接入栈
                computeStack.push(Integer.valueOf(exp));
            } else {
                Integer num1 = computeStack.pop();
                Integer num2 = computeStack.pop();
                if ("+".equals(exp)) {
                    computeStack.push(num2 + num1);
                } else if ("-".equals(exp)) {
                    computeStack.push(num2 - num1);
                } else if ("*".equals(exp)) {
                    computeStack.push(num2 * num1);
                } else if ("/".equals(exp)) {
                    computeStack.push(num2 / num1);
                } else if ("%".equals(exp)) {
                    computeStack.push(num2 % num1);
                }
            }
        }
        return computeStack.pop();
    }

    private static Stack<String> getSuffixExpression(String expression) {
        // 将操作符与操作数分开为数组形式
        String[] expressions = expression.replaceAll("(\\D)", "#$1#").replaceAll("##", "#").split("#");

        // 操作符栈
        Stack<String> operationalCharacterStack = new Stack<String>();
        // 结果栈
        Stack<String> resultStack = new Stack<String>();
        for (String exp : expressions) {
            if ("".equals(exp)) {
                continue;
            }
            if (Character.isDigit(exp.charAt(0))) {
                // 如果是数字，直接输出
                resultStack.push(exp);
            } else if ("(".equals(exp) || "[".equals(exp)) {
                // 如果遇到开始括号，入操作符栈
                operationalCharacterStack.push(exp);
            } else if (")".equals(exp) || "]".equals(exp)) {
                // 如果遇到结果操作符号，出栈，直到遇到开始操作符为止
                String start;
                if (")".equals(exp)) {
                    start = "(";
                } else {
                    start = "[";
                }
                while (!operationalCharacterStack.peek().equals(start)) {
                    resultStack.push(operationalCharacterStack.pop());
                }
                // 最后一个是开始括号，不需要，直接舍弃
                operationalCharacterStack.pop();
            } else {
                // 遇到其他操作符的时候,需要把优先级相同或更高的操作符出栈
                if ("+-".contains(exp)) {
                    // 如果是+-,则需要把+-*/%全部出栈
                    while (!operationalCharacterStack.isEmpty() && "+-*/%".contains(operationalCharacterStack.peek())) {
                        resultStack.push(operationalCharacterStack.pop());
                    }
                } else if ("*/%".contains(exp)) {
                    // 如果是*/%,则需要把*/%全部出栈
                    while (!operationalCharacterStack.isEmpty() && "*/%".contains(operationalCharacterStack.peek())) {
                        resultStack.push(operationalCharacterStack.pop());
                    }
                }
                operationalCharacterStack.push(exp);
            }
        }
        while (!operationalCharacterStack.isEmpty()) {
            resultStack.push(operationalCharacterStack.pop());
        }
        Collections.reverse(resultStack);
        return resultStack;
    }

}
